package com.summer.algorithm;

import java.util.ConcurrentModificationException;
import java.util.Iterator;

public class StaticLinkedList<T> implements Iterable<T>{
	
	private final int MAX = 100;
	private final int FIRS_INDEX = 0;
	private final int TAIL_INDEX = MAX-1;
 
	@SuppressWarnings("unchecked")
	private Node<T>[] nodeList = new Node[MAX];	
	{
		for(int index = 0;index < MAX-1;index++){
			Node<T> node = new Node<T>(null);
			node.nextIndex  = index + 1;
			nodeList[index] = node;
		}
		Node<T> node = new Node<T>(null);
		node.nextIndex  = 0;
		nodeList[TAIL_INDEX] = node;
	}
	
	private int mallocListSpace(){
		int lastNodeIndex = nodeList[FIRS_INDEX].nextIndex;
		if(lastNodeIndex != 0) {
			nodeList[FIRS_INDEX].nextIndex = nodeList[lastNodeIndex].nextIndex;
		}
		return lastNodeIndex;
	}
	
	public int countSize(){
		int index = TAIL_INDEX;
		int count = 0;
		while(nodeList[index].nextIndex!=0){
			index = nodeList[index].nextIndex;
			count++;
		}
		return count;
	}
	
	private void checkOverstep(int index){
		if(index < 1 || index > countSize()+1)
			throw new RuntimeException("插入位置错误");
	}
	
	private void recycling(int index){
		nodeList[index].nextIndex = nodeList[FIRS_INDEX].nextIndex;
		nodeList[FIRS_INDEX].nextIndex = index;
	}
	
	public void insertNode(int index,T data){
		
		checkOverstep(index);
		
		int newNodeIndex = mallocListSpace();
		if(newNodeIndex == 0)
			throw new RuntimeException("列表已满");
		
		int pre = TAIL_INDEX;
		for(int i = 1; i<index; i++)
			pre = nodeList[pre].nextIndex;
		
		nodeList[newNodeIndex].nextIndex = nodeList[pre].nextIndex;
		nodeList[newNodeIndex].data 	 = data;
		nodeList[pre].nextIndex 		 = newNodeIndex;
		
	}
	
	public T deleteNode(int index){
		checkOverstep(index);
		
		int pre = TAIL_INDEX;
		for(int i = 1; i<index; i++)
			pre = nodeList[pre].nextIndex;
		
		int current = nodeList[pre].nextIndex;
		nodeList[pre].nextIndex = nodeList[current].nextIndex;
		T data = nodeList[current].data;
		recycling(current);
		
		return data;
	}
	
	
	//---------------------------------------------------------------------------------------------------
	
	public boolean add(T data){
		insertNode(countSize()+1, data);
		return true;
	}

	@Override
	public Iterator<T> iterator() {
		// TODO Auto-generated method stub
		return new SimpleIterator();
	}

	
	public class SimpleIterator implements Iterator<T> {
		
		int index = TAIL_INDEX;
		int expectedModCount = countSize();
		
		@Override
		public boolean hasNext() {
			boolean hasNext = nodeList[index].nextIndex!=0;
			if(hasNext)
				index = nodeList[index].nextIndex;
			return hasNext;
		}
		@Override
		public T next() {
			checkForComodification();
			T data = nodeList[index].data;
			return data;
		}
	
		private void checkForComodification(){
			if(countSize() != expectedModCount)
				throw new ConcurrentModificationException();
		}
		
	}
	
	
	//---------------------------------------------------------------------------------------------------
	
	private final static class Node<T>{
		public int nextIndex;
		public T   data;
		public Node(T data){
			this.data = data;
		}
	}









	
}
